package cn.moefly.algorithm.string;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

/**
 * 编辑距离，又称Levenshtein距离（也叫做Edit Distance），
 * 是指两个字串之间，由一个转成另一个所需的最少编辑操作次数，
 * 如果它们的距离越大，说明它们越是不同。
 * 许可的编辑操作包括将一个字符替换成另一个字符，插入一个字符，删除一个字符。
 */
public class LevenshteinDistance {

    public int solution(String s1, String s2){
        if (s1.equals(s2)){
            return 0;
        }

        var char1 = s1.toCharArray();
        var char2 = s2.toCharArray();

        int[][] matrix = new int[char1.length+1][char2.length+1];

        IntStream.range(0, matrix.length).forEach(i->matrix[i][0] = i);
        IntStream.range(0, matrix[0].length).forEach(i->matrix[0][i] = i);


        for (int i = 1; i <= char1.length; i++) {
            for (int j = 1; j <= char2.length; j++) {
                int t = char1[i-1] == char2[j-1]?0:1;

                int a = matrix[i-1][j] + 1;
                int b = matrix[i][j-1] + 1;
                int c = matrix[i-1][j-1] + t;
                matrix[i][j] = Integer.min(a,Integer.min(b,c));
            }
        }

        return matrix[char1.length][char2.length];
    }

    /**
     * 网上的一个demo，不过算法好像有点问题
     * https://zhuanlan.zhihu.com/p/104190037
     * @param input
     * @param target
     * @return
     */
    public int getEditDistance(String input, String target){
        int m = input.length();
        int n = target.length();
        if(m == 0) return n;
        if(n == 0) return m;
        int[][] matrix = new int[m][n];
        for(int i = 0; i < m; i++){
            matrix[i][0] = i;
        }
        for(int j = 0; j < n; j++){
            matrix[0][j] = j;
        }
        for(int i = 1; i < m; i++)
            for(int j = 1; j < n; j++){
                int t = input.charAt(i) == target.charAt(j) ? 0 : 1;
                matrix[i][j] = Math.min(matrix[i - 1][j - 1] + t,
                        Math.min(matrix[i - 1][j] + 1,matrix[i][j - 1] + 1));
            }
        return matrix[m - 1][n - 1];
    }

    public static void main(String[] args) {
        System.out.println(new LevenshteinDistance().solution("horse","ros"));
        System.out.println(new LevenshteinDistance().solution("intention","execution"));
        System.out.println(new LevenshteinDistance().solution("ctiab","ctaa"));
    }
}
